// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-27 19:43
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.DynamicPlan.threeLeafTrains;

import java.util.HashMap;
import java.util.Map;

public class LongestSubsequence {
    /**
     * 最长等差子数列 》》动态规划
     * 增添维度记录状态，因为给定了数组及定差
     */
    public int longestSubsequenceT(int[] arr, int difference) {
        int n = arr.length;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        int[][] f = new int[n + 1][2];
        f[0][1] = 1;
        map.put(arr[0], 0);
        for (int i = 1; i < n; i++) {
            f[i][0] = Math.max(f[i - 1][1], f[i - 1][0]);
            f[i][1] = 1;
            int prev = arr[i] - difference;
            if (map.containsKey(prev)) {
                f[i][1] = Math.max(f[i][1], f[map.get(prev)][1] + 1);
            }
            map.put(arr[i], i);
        }
        return Math.max(f[n - 1][0], f[n - 1][1]);
    }


    /**
     * 状态优化
     */
    public int longestSubsequence(int[] arr, int difference) {
        Map<Integer, Integer> map = new HashMap<>();
        int ans = 1;
        for (int i : arr) {
            map.put(i, map.getOrDefault(arr[i] - difference, 0) + 1);
            ans = Math.max(ans, map.get(i));
        }
        return ans;
    }
}